#include<bits/stdc++.h>
#define int long long
#define il inline
#define ct const
#define dl double
#define pk push_back
#define fi first
#define se second
#define pii pair<int,int>
#define mod 1000000007
#define N 100010
using namespace std;
il int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);ch=getchar();
	}
	return x*f;
}
char f__[40];
il void write(int x){
	int cnt=0;
	if(x<0){
		putchar('-');x=-x;
	}
	if(!x) putchar('0');
	while(x){
		f__[cnt++]=x%10+'0';x/=10;
	}
	while(cnt) putchar(f__[--cnt]);
}
int n,T,f1[N],f0[N],f11[N];
char p[N];
string S[15];
signed main(){
	freopen("brotherhood.in","r",stdin);
	freopen("brotherhood.out","w",stdout);
    n=read();T=read();
    S[1]="0";S[2]="1";
    for(int i=3;i<=10;++i) S[i]=S[i-1]+S[i-2];
    f1[1]=0;f1[2]=1;f0[1]=1;f0[2]=0;f11[1]=0;f11[2]=0;
    for(int i=3;i<=1e5;++i){
        f1[i]=(f1[i-1]+f1[i-2])%mod;
        f0[i]=(f0[i-1]+f0[i-2])%mod;
        f11[i]=(f11[i-1]+f11[i-2]+(i>3&&(i&1)))%mod;
    }
    for(int t=1;t<=T;++t){
        scanf(" %s",p+1);
        int flag=1,lst=p[1]-'0',sz=strlen(p+1);
        for(int i=2;i<=sz;++i) if(p[i]-'0'!=lst){
            flag=0;break;
        }
        if(!flag&&n<=10&&sz<=100&&T<=10){
            int ans=0;
            for(int i=1;i<=n;++i){
                int sz_=S[i].size();
                for(int j=0;j<sz_-sz;++j){
                    int flag=1;
                    for(int k=j;k<j+sz;++k) if(S[i][k]!=p[k-j+1]){
                        flag=0;break;
                    }
                    ans+=flag;
                }
            }
            write(ans);
        }
        else{
            if(lst){
                if(sz==1) write(f1[n]);
                else if(sz==2) write(f11[n]);
                else putchar('0');
            }
            else{
                if(sz==1) write(f0[n]);
                else putchar('0');
            }
        }
        putchar('\n');
    }
	return 0;
}